//主要用到的有预处理阶乘以及通过快速幂求阶乘的逆元算1e5以下的组合数
//还有通过卢卡斯定理拆分1e5以上的组合数
#include <iostream>
using namespace std;

typedef long long ll;

const int N = 100010;

int n, p; //获取输入
ll a, b;
ll fact[N], infact[N]; //和上一题一样，预处理出阶乘方便求解

ll quick_pow(ll a, ll b, int p) //快速幂
{
    ll res = 1, t = a;
    while (b)
    {
        if (b & 1)
            res = res * t % p;
        t = t * t % p;
        b >>= 1;
    }
    return res;
}

void init(int n, int p) //初始化，n为初始化到的位置，因为p在变化，所以每次都要初始化
{
    infact[0] = fact[0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        fact[i] = fact[i - 1] * i % p;
        infact[i] = quick_pow(fact[i], p - 2, p);
    }
    return;
}

int C(int a, int b, int p) //第二题的那种组合方式
{
    if (a < b)
        return 0; //边缘值处理，代表这个组合无意义，因为Lucas定理中可能拆分中这种
    init(a, p);
    return fact[a] * infact[b] % p * infact[a - b] % p;
}

int lucas(ll a, ll b, int p) //Lucas拆分
{
    if (a < p && b < p)    //既不可再分
        return C(a, b, p); //那就直接用第二题的组合方式
    else
        return (ll)C(a % p, b % p, p) * lucas(a / p, b / p, p) % p; //否则就Lucas再拆分一次
                                                                    //注意这里要强制转化一下，否则会爆ll
}

int main()
{
    freopen("cin.txt", "r", stdin);
    cin >> n;
    while (n--)
    {
        cin >> a >> b >> p;
        cout << lucas(a, b, p) << endl;
    }
    return 0;
}